package com.example.bst;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉树的基本算法
 *
 * @Date 2022/4/2
 * @Created by Jonathan
 */
public class BST {

    static class Node {
        Integer value;
        Node right;
        Node left;
    }

    /*
    非递归实现二叉树的先序、中序、后序遍历
    1) 任何递归函数都可以改成非递归
    2) 自己设计压栈来实现
     */

    /*
     * 实现二叉树的层次遍历
     * 1)其实就是宽度优先遍历
     * 2)可以通过设置flag变量的方式，来发现某一层结束(看题目，比如统计二叉树的宽度)
     *
     */

    public Integer getMaxWidth(Node head) {
        // 判空
        if (head == null) return 0;
        // 队列
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        Node curEnd = head; // 初始时当前行的结束点就是head
        Node nextEnd = null; // 下一行的结束点
        int max = 0; //记录最大的宽度
        int curLevelNodes = 0; // 当前节点的层数
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            // 左孩子入队 更新nextEnd
            if (cur.left != null) {
                queue.add(cur.left);
                nextEnd = cur.left;
            }
            // 右孩子入队 更新nextEnd
            if (cur.right != null) {
                queue.add(cur.right);
                nextEnd = cur.right;
            }
            // 更新当前行的节点数
            curLevelNodes++;
            // 当前行最后一个节点
            if (cur == curEnd) {
                max = Math.max(max, curLevelNodes);
                curLevelNodes = 0;
                curEnd = nextEnd;
            }
        }
        return max;
    }




}
